package leetcode_1001_1100;

import javax.smartcardio.ATR;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LeeCode_1039_2_timeout {
    public static void main(String[] args) {
//        System.out.println(minScoreTriangulation(new int[]{1, 2, 3}));
//        System.out.println(minScoreTriangulation(new int[]{3,7,4,5}));
//        System.out.println(minScoreTriangulation(new int[]{1,3,1,4,1,5}));
//        System.out.println(minScoreTriangulation(new int[]{2,1,4,4}));
        System.out.println(minScoreTriangulation(new int[]{5,5,5,4,2,5}));
        System.out.println(minScoreTriangulation(new int[]{1,1,1,1,1,1}));
    }
    private static int minScoreTriangulation(int[] values) {
        Map<String, Integer> map = new HashMap<>();
        int fa = fa(values,map);
        return fa;
    }
    private static int fa(int[] values,Map<String, Integer> map){
        int len = values.length;
        StringBuilder key = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            key.append(values[i]);
        }
        if (len < 3) {
            map.put(key.toString(), 0);
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                for (int k = j + 1; k < len; k++) {
                    int tag = values[i] * values[j] * values[k];
                    int[] arr1 = Arrays.copyOfRange(values, i, j +1);
                    int[] arr2 = Arrays.copyOfRange(values, j, k + 1);
                    int[] arr3 = new int[len - k + i + 1];
                    int n = 0;
                    for (int m = k; m < len; m++) {
                        arr3[n] = values[m];
                        n++;
                    }
                    for (int m = 0; m <= i; m++) {
                        arr3[n] = values[m];
                        n++;
                    }
                    StringBuilder key1 = new StringBuilder();
                    for (int m = 0; m < arr1.length; m++) {
                        key1.append(arr1[m]);
                    }
                    StringBuilder key2 = new StringBuilder();
                    for (int m = 0; m < arr2.length; m++) {
                        key2.append(arr2[m]);
                    }
                    StringBuilder key3 = new StringBuilder();
                    for (int m = 0; m < arr3.length; m++) {
                        key3.append(arr3[m]);
                    }
                    int min1 = map.containsKey(key1.toString()) ? map.get(key1.toString()) : fa(arr1, map);
                    int min2 = map.containsKey(key2.toString()) ? map.get(key2.toString()) : fa(arr2, map);
                    int min3 = map.containsKey(key3.toString()) ? map.get(key3.toString()) : fa(arr3, map);
//                    int min1 = fa(arr1, map);
//                    int min2 = fa(arr2, map);
//                    int min3 = fa(arr3, map);
                    res = Math.min(res, tag + min1 + min2 + min3);
                }
            }
        }
        map.put(key.toString(), res);
        return res;
    }

    private static int f2(int[] values, Map<String, Integer> map){
        int len = values.length;
        if (len < 3)
            return 0;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                for (int k = j + 1; k < len; k++) {
                    int tag = values[i] * values[j] * values[k];
                    int min1,min2,min3;
                    String key1 = i + "," + j;
                    String key2 = j + "," + k;
                    String key3 = k + "," + i;
                    if (map.containsKey(key1)){
                        min1 = map.get(key1);
                    }else {
                        int[] arr1 = Arrays.copyOfRange(values, i, j +1);
                        min1 = f2(arr1, map);
                        map.put(key1, min1);
                    }
                    if (map.containsKey(key2)){
                        min2 = map.get(key2);
                    }else {
                        int[] arr2 = Arrays.copyOfRange(values, j, k + 1);
                        min2 = f2(arr2, map);
                        map.put(key2, min2);
                    }
                    if (map.containsKey(key3)){
                        min3 = map.get(key3);
                    }else {
                        int[] arr3 = new int[len - k + i + 1];
                        int n = 0;
                        for (int m = k; m < len; m++) {
                            arr3[n] = values[m];
                            n++;
                        }
                        for (int m = 0; m <= i; m++) {
                            arr3[n] = values[m];
                            n++;
                        }
                        min3 = f2(arr3, map);
                        map.put(key3, min3);
                    }
                    res = Math.min(res, tag + min1 + min2 + min3);
                }
            }
        }
        return res;
    }
}
